package code701_800.code80_90;

import java.util.ArrayList;
import java.util.List;

/**
 * 给定一个字符串S，通过将字符串S中的每个字母转变大小写，我们可以获得一个新的字符串。返回所有可能得到的字符串集合。
 *
 *  
 *
 * 示例：
 * 输入：S = "a1b2"
 * 输出：["a1b2", "a1B2", "A1b2", "A1B2"]
 *
 * 输入：S = "3z4"
 * 输出：["3z4", "3Z4"]
 *
 * 输入：S = "12345"
 * 输出：["12345"]
 *
 * S 的长度不超过12。
 * S 仅由数字和字母组成。
 */
public class _784letterCasePermutation {

    /**
     * 思考：第一步骤使用了dfs的全排列方法，不通后看了题解，这就是个字符串的问题，不是全排列的问题！！
     *
     * 执行用时：     * 8 ms     * , 在所有 Java 提交中击败了     * 40.82%     * 的用户
     * 内存消耗：     * 39.2 MB     * , 在所有 Java 提交中击败了     * 42.16%     * 的用户
     * @param s
     * @return
     */
    public List<String> letterCasePermutation(String s) {
        /*List<String> result = new ArrayList<>();
        int len = s.length();
        if(len == 0)return result;
        boolean[] isUsed = new boolean[len];
        StringBuffer path = new StringBuffer();
        dfs(s,len,0,path,isUsed,result);
        return result;*/

        List<StringBuilder> ans = new ArrayList();
        ans.add(new StringBuilder());

        for (char c: s.toCharArray()) {
            int n = ans.size();
            if (Character.isLetter(c)) {
                for (int i = 0; i < n; ++i) {
                    ans.add(new StringBuilder(ans.get(i)));
                    ans.get(i).append(Character.toLowerCase(c));
                    ans.get(n+i).append(Character.toUpperCase(c));
                }
            } else {
                for (int i = 0; i < n; ++i)
                    ans.get(i).append(c);
            }
        }
        List<String> finalans = new ArrayList();
        for (StringBuilder sb: ans)
            finalans.add(sb.toString());
        return finalans;
    }

    /**
     * 此路不通
     */
    /*public void dfs(String s,int len, int depth, StringBuffer path, boolean[] isUsed,List<String> result){
        if(depth == len){
            result.add(path.toString());
            return;
        }
        for (int i = 0; i < len; i++) {
            if(isUsed[i])continue;
            char temp = s.charAt(i);
            if(temp<57){
                isUsed[i] = true;
                depth++;
                continue;
            }else if(temp<97){
                //大写字母
                path.append(temp);
                isUsed[i] = true;
                dfs(s,len,depth+1,path,isUsed,result);
                path.substring(0,path.length()-1);
                isUsed[i] = false;

                isUsed[i] = true;
                path.append(temp+32);
                dfs(s,len,depth+1,path,isUsed,result);
                path.substring(0,path.length()-1);
                isUsed[i] = false;
            }else {
                // 小写字母
                path.append(temp);
                isUsed[i] = true;
                dfs(s,len,depth+1,path,isUsed,result);
                path.substring(0,path.length()-1);
                isUsed[i] = false;
                isUsed[i] = true;
                path.append(temp-32);
                dfs(s,len,depth+1,path,isUsed,result);
                path.substring(0,path.length()-1);
                isUsed[i] = false;
            }
        }
    }*/

    /**
     * 用dfs递归也是可以写的
     *
     * 执行用时：     * 1 ms     * , 在所有 Java 提交中击败了     * 100.00%     * 的用户
     * 内存消耗：     * 39.3 MB     * , 在所有 Java 提交中击败了     * 34.71%     * 的用户
     * @param S
     * @return
     */
    List<String> res = new ArrayList<>();
    public List<String> letterCasePermutation2(String S) {
        char[] chs = S.toCharArray();
        int n = S.length();
        dfs(chs,n,0);
        return res;
    }

    public void dfs(char[] chs,int len,int begin){
        res.add(new String(chs));
        for (int i = begin; i < len; i++) {
            char temp = chs[i];
            if(!Character.isDigit(temp)){
                chs[i] = (char)(chs[i]-'a'>=0?chs[i]-32:chs[i]+32);
                dfs(chs,len,i+1);
                chs[i] = temp;
            }
        }
    }

}
